// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

// 算法思路总结：
// 1. 使用状态机动态规划处理含手续费的股票交易
// 2. 维护两种状态：持有股票(cur0)和不持有股票(cur1)
// 3. 状态转移考虑买入、卖出和手续费
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
        int m = prices.size();

        if (m == 0) return 0;
        if (m == 1) return 0;

        int prev0 = -prices[0], prev1 = 0;
        int cur0, cur1;
        for (int i = 1 ; i < m ; i++)
        {
            cur0 = max(prev0, prev1 - prices[i]);
            cur1 = max(prev1, prev0 + prices[i] - fee);

            prev0 = cur0;
            prev1 = cur1;
        }
        return cur1;
    }
};

int main()
{
    vector<int> v1 = {1, 3, 2, 8, 4, 9}, v2 = {1,3,7,5,10,3};
    int f1 = 2, f2 = 3;
    Solution sol;

    cout << sol.maxProfit(v1, f1) << endl;
    cout << sol.maxProfit(v2, f2) << endl;

    return 0;
}